% -*- coding:utf-8 -*-

\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[spanish]{babel}

\usepackage[bookmarks, hyperfootnotes=false, colorlinks=true,%
            urlcolor=blue, linkcolor=black,  citecolor=black,%
            pagecolor=black, anchorcolor=black, breaklinks=true]{hyperref}

\usepackage{enumerate}
\usepackage{eurosym}
\usepackage{graphicx}
\usepackage{times}
\usepackage{color}
\usepackage{array}
\usepackage{colortbl}
\usepackage{longtable}

\usepackage{fancyhdr}
\usepackage{fancybox}
\usepackage{listings}
\usepackage{subfigure}
\usepackage{hyperref}
\usepackage{tikz}

\usepackage{epsfig}
\usepackage{float}
\usepackage{amsmath}
\usepackage{lscape}

\setlength{\headheight}{16pt}
\setlength{\oddsidemargin}{17pt}
\setlength{\textwidth}{420pt}
\setlength{\topmargin}{0pt}
\setlength{\textheight}{600pt}
\setlength{\marginparwidth}{55pt}


\newcommand{\fsm}{\emph{FSM}}
\newcommand{\ice}{\emph{ICE}}
\newcommand{\icefield}{\emph{IceField}}
\newcommand{\slice}{\emph{Slice}}

\pagestyle{fancy}

\renewcommand{\footrulewidth}{0.5pt}

\fancyhead[R]{Práctica 1-Entrega final}
\fancyhead[L]{Inteligencia Artificial}
\fancyfoot[R]{Manuel J. Abaldea Gª-Pliego}
\fancyfoot[L]{Entrega final}


\newenvironment{float_code} {
      \begin{lst}
      }
      {
      \end{lst}
      }


\newfloat{lst}{H}{lop}[section]
\floatname{lst}{Listado}
\floatplacement{codigo}{!htb}
\floatstyle{plain}


\begin{document}

\begin{center}
\begin{Large}\textit{\textquotedblleft
Inteligencia Artificial \ \ Práctica 1
\textquotedblright}\end{Large}
\end{center}

\vspace*{0.5cm}

\begin{flushleft}
\begin{large}
\textit{
Alumno: Manuel J. Abaldea Gª-Pliego
}
\end{large}
\end{flushleft}

\vspace*{1cm}

\section{Casos de estudio}

\subsection{(CA) Imagen pequeña (aprox 50x50)}
\begin{figure}[!h]
  \center
  \includegraphics[scale=4.4]{50x50.png}
  \caption{Mapa 50x50}
\end{figure}

 \begin{tabular}[!ht]{|c|c|c|c|} \hline
    \textbf{algoritmo} & \textbf{nodos desplegados} & \textbf{tiempo
      de búsqueda} & \textbf{coste de la solución} \\ \hline
    Anchura & 28604 & 0,22 seg & 965  \\ \hline
    Profundidad S. & 195 & < 0,01 seg & 885  \\ \hline
    Profundidad A. & 195 & < 0,01 seg & 885 \\ \hline
    Profundidad I. & 195 & < 0,01 seg & 885 \\ \hline
    Coste Uniforme & 2487 & < 0,01 seg & 335 \\ \hline
    A* Euclidea & 2599 & < 0,01 seg & 335 \\ \hline
    A* Manhattan & 2664 & < 0,01 seg & 335 \\ \hline
  \end{tabular}

\clearpage

\subsection{(CB) Imagen mediana (aprox 200x200)}
\begin{figure}[!h]
  \center
  \includegraphics[scale=1.4]{200x200.png}
  \caption{Mapa 200x200}
\end{figure}

 \begin{tabular}[!ht]{|c|c|c|c|} \hline
    \textbf{algoritmo} & \textbf{nodos desplegados} & \textbf{tiempo
      de búsqueda} & \textbf{coste de la solución} \\ \hline
    Anchura & > 2000000 & --- & ---  \\ \hline
    Profundidad S. & 795 & < 0,01 seg & 4643  \\ \hline
    Profundidad A. & 795 & < 0,01 seg & 4643 \\ \hline
    Profundidad I. & 795 & < 0,01 seg & 4643 \\ \hline
    Coste Uniforme & 37250 & 0,24 seg & 779 \\ \hline
    A* Euclidea & 31500 & 0,23 seg & 779 \\ \hline
    A* Manhattan & 28692 & 0,21 seg & 779 \\ \hline
  \end{tabular}

\clearpage
\subsection{(CC) Imagen grande (aprox 1024x1024)}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.3]{1024x1024.png}
  \caption{Mapa 1024x1024}
\end{figure}

 \begin{tabular}[!ht]{|c|c|c|c|} \hline
    \textbf{algoritmo} & \textbf{nodos desplegados} & \textbf{tiempo
      de búsqueda} & \textbf{coste de la solución} \\ \hline
    Anchura & --- & --- & ---  \\ \hline
    Profundidad S. & 4091 & 0,9 seg & 29208  \\ \hline
    Profundidad A. & 4091 & 0,9 seg & 29208 \\ \hline
    Profundidad I. & 4091 & 0,9 seg & 29208 \\ \hline
    Coste Uniforme & 1048576 & 16,62 seg & 5319 \\ \hline
    A* Euclidea & 1104855 & 17,58 seg & 5319 \\ \hline
    A* Manhattan & 1177759 & 17,67 seg & 5319 \\ \hline
  \end{tabular}

\clearpage

\section{Construcción de la solución}
\subsection{Métodos}
\subsubsection{Sin Información}
Estos algoritmos de búsqueda tienen la misma función base, mientras
existan nodos en mi frontera, si no he encontrado solución, seguir expandiendo:
\begin{verbatim}
while (!frontera.empty()) {
    Nodo* nodo_actual = frontera.begin()->second;
    frontera.erase(frontera.begin());
    if(nodo_actual->esSolucion(pos_fin)){
      Crear_Solucion(sol,*nodo_actual);
      break;
    }
    else{
      if(Expandir(mapa_aux,mapa,X,Y,max_dimension,*nodo_actual,frontera,
		  visitados,pos_fin,estrategia))
	nodos_cont ++;
    }
}
return sol;
\end{verbatim}
La diferencia está en la función que utilizamos para expandir la
frontera. Se ha codificado un puntero a función, de modo que el
programa siempre hará lo mismo, solo que la función a la que invoca
cambia en cada algoritmo:
\begin{verbatim}
float F_Anchura(Nodo &nodo_aux){
  return nodo_aux.get_prof();
}
float F_Prof(Nodo &nodo_aux){
  return -(nodo_aux.get_prof());
}
\end{verbatim}
Como se puede ver en el código, en el caso de \emph{búsqueda en anchura} se
expandirá la frontera utilizando la profundidad, se expanden primero
los nodos menos profundos. En \emph{búsqueda en profundidad} se utiliza la
profundidad negada, desplegando primero los nodos más profundos.
Para los algoritmos de profundidad \emph{acotada} e \emph{iterativa}, a la hora de
invocar la función de búsqueda, limitaremos el nivel de profundidad a
la cota dada, e iremos incrementando esta cota en el caso de búsqueda
iterativa.
\begin{verbatim}
while(cont_itera <= num_itera){
  sol_encontrada = Busqueda(map, posIni, posFin, estrategia, cota, aumento_cota, num_itera);
  if (sol_encontrada)
     break;
  else{
     cota += aumento_cota;
     cont_itera++;
  }
}
\end{verbatim}

\subsubsection{Con Información}
La diferencia de estos algoritmos con información a los anteriores sin
información sigue siendo en la función que utilizamos para expandir la
frontera:
\begin{verbatim}
float F_CosteU(Nodo &nodo_aux, int *posFin){
    return nodo_aux.get_cost();
}
float F_Euclidea(Nodo &nodo_aux, int *posFin){
  float dist, cost;
  dist = sqrt(pow((posFin[0] - nodo_aux.get_coX()),2) +
	      pow((posFin[1] - nodo_aux.get_coY()),2));
  cost = nodo_aux.get_cost() + dist;
  return cost;
}
float F_Manhattan(Nodo &nodo_aux, int *posFin){
  float dist, cost;
  dist = abs(posFin[0] - nodo_aux.get_coX()) +
         abs(posFin[1] - nodo_aux.get_coY());
  cost = nodo_aux.get_cost() + dist;
  return cost;
}
\end{verbatim}
En el caso de \emph{coste uniforme} la función es la misma que en
anchura, expandimos primero los nodos menos profundos, pero la
diferencia es que si expandimos un nodo con una posición ya visitada
nos quedaremos con el nodo con menor coste y no seguiremos expandiendo
el que tenga mayor coste. La diferencia con los algoritmos \emph{A*}
está clara, se penaliza con mayor coste a los nodos que más se separen
de la distancia más corta (Euclidea o Manhattan).

\clearpage

\subsection{Datos a comparar}
\subsubsection{Solución obtenida}
A continuación se muestran las figuras con las soluciones obtenidas con
los distintos algoritmos:
\begin{figure}[!h]
  \center
  \includegraphics[scale=4.4]{solAn50x50.png}
  \caption{Mapa 50x50 solucionado con algoritmo de búsqueda en anchura}
\end{figure}

La solución de los algoritmos de profundidad es igual en los casos
simple, acotada e iterativa ya que en el código el orden de expansión
es derecha, abajo, izquierda, arriba.
\begin{figure}[!h]
  \center
  \includegraphics[scale=4.4]{solP50x50.png}
  \caption{Mapa 50x50 solucionado con algoritmo de profundidad simple, acotada e iterativa}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=1.2]{solP200x200.png}
  \caption{Mapa 200x200 solucionado con algoritmo de profundidad simple, acotada e iterativa}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.25]{solP1024x1024.png}
  \caption{Mapa 1024x1024 solucionado con algoritmo de profundidad simple, acotada e iterativa}
\end{figure}

\clearpage

A continuación mostramos las soluciones de los algoritmos de coste
uniforme y los A*. Se puede comprobar que estas soluciones coinciden
ya que son la solución óptima.
\begin{figure}[!h]
  \center
  \includegraphics[scale=4.4]{solCU50x50.png}
  \caption{Mapa 50x50 solucionado con algoritmo de coste uniforme}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=1.2]{solCU200x200.png}
  \caption{Mapa 200x200 solucionado con algoritmo de coste uniforme}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.25]{solCU1024x1024.png}
  \caption{Mapa 1024x1024 solucionado con algoritmo de coste uniforme}
\end{figure}

\begin{figure}[!h]
  \center
  \includegraphics[scale=4.4]{solAE50x50.png}
  \caption{Mapa 50x50 solucionado con algoritmo A* distancia Euclidea
    y Manhattan}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=1.4]{solCU200x200.png}
  \caption{Mapa 200x200 solucionado con algoritmo A* distancia Euclidea}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{solCU1024x1024.png}
  \caption{Mapa 1024x1024 solucionado con algoritmo A* distancia Euclidea}
\end{figure}

\clearpage

\subsection{Memoria utilizada}
Hemos medido la memoria utilizada con los nodos desplegados por cada
algoritmo, dando como resultado:
\begin{center}
   \begin{tabular}[!ht]{|c|c|c|c|c|c|c|c|} \hline
    \textbf{Imagen} & \textbf{BAn} & \textbf{BPs} & \textbf{BPa} &
    \textbf{BPi} & \textbf{BCu}  & \textbf{BAe} & \textbf{BAm}\\
    \hline

    \textbf{50x50} & 28604 & 195 & 195 & 195 & 2487 & 2599 & 2664  \\ \hline
    \textbf{200x200} & >2000000 & 795 & 795 & 795 & 37250 & 31500 & 28692  \\ \hline
    \textbf{1024x1024} & --- & 4091 & 4091 & 4091 & 1048576 & 1104855 & 1177759  \\ \hline
  \end{tabular}
\end{center}


Para la búsqueda en anchura tan solo se han obtenido resultados para la
imagen más pequeña, la razón es que el algoritmo recorre todas las
opciones incluyendo pasar varias veces por el mismo punto. Si se
limita esta opción sí que se obtendrían resultados, pero entonces el
algoritmo no sería anchura sin información. Para imágenes de más de
100x100 en el ordenador de pruebas (Intel Pentium 4, 2Gb RAM) colapsaba a
los 5 minutos de ejecución con más de 2000000 de nodos expandidos.

Comentar también que los algoritmos de profundidad acotada e
iterativa tienen los mismos resultados que el de profundidad
simple. Esto es porque el código expande los nodos en orden derecha,
abajo, izquierda, arriba; de modo que la primera solución que
encuentra es muy cercana (es el algoritmo más rápido y que menos nodos
despliega a causa de la especificación del código) e incluir una cota
conlleva a no encontrar solución.

Comparando los algoritmos con información hay casos en los que el
algoritmo de \emph{coste uniforme} expande menos nodos que el
\emph{A*}, cuando en teoría debería ser al contrario. La razón es que
la solución se aleja del camino más corto, ya sea utilizando distancia
euclidea o manhattan. Sería aconsejable comparar con varias imágenes
del mismo tamaño y obtener resultados estadísticos.

\subsection{Tiempo utilizado}

\begin{center}
   \begin{tabular}[!ht]{|c|c|c|c|c|c|c|c|} \hline
    \textbf{Imagen} & \textbf{BAn} & \textbf{BPs} & \textbf{BPa} &
    \textbf{BPi} & \textbf{BCu}  & \textbf{BAe} & \textbf{BAm}\\
    \hline

    \textbf{50x50} & 0,22 seg & < 0,01 seg & < 0,01 seg & < 0,01 seg & < 0,01 seg & < 0,01 seg & < 0,01 seg  \\ \hline
    \textbf{200x200} & --- & < 0,01 seg & < 0,01 seg & < 0,01 seg & 0,24 seg & 0,23 seg & 0,21 seg  \\ \hline
    \textbf{1024x1024} & --- & 0,09 seg4091 & 0,09 seg4091 & 0,09 seg & 16,62 seg & 17,58 seg & 17,67 seg  \\ \hline
  \end{tabular}
\end{center}

\subsection{Valor de la solución}

\begin{center}
   \begin{tabular}[!ht]{|c|c|c|c|c|c|c|c|} \hline
    \textbf{Imagen} & \textbf{BAn} & \textbf{BPs} & \textbf{BPa} &
    \textbf{BPi} & \textbf{BCu}  & \textbf{BAe} & \textbf{BAm}\\
    \hline

    \textbf{50x50} & 965 & 885 & 885 & 885 & 335 & 335 & 335  \\ \hline
    \textbf{200x200} & --- & 4643 & 4643 & 4643 & 779 & 779 & 779  \\ \hline
    \textbf{1024x1024} & --- & 29208 & 29208 & 29208 & 5319 & 5319 & 5319  \\ \hline
  \end{tabular}
\end{center}

\clearpage

\subsection{Gráficos}

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{Gnodos_desplegados.png}
  \caption{Memoria utilizada. Nodos desplegados}
\end{figure}

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{Gtiempos.png}
  \caption{Tiempo tardado en encontrar solución}
\end{figure}

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{Gcoste_sol.png}
  \caption{Coste de la solución}
\end{figure}

\clearpage

\section{Mejora de soluciones}
Los siguientes algoritmos son algoritmos de búsqueda local, que
funcionan con un solo estado actual más que múltiples caminos y
trabaja con vecinos del estado actual.

\subsection{Métodos}
\subsubsection{Ascenso de colinas}
La búsqueda mediante el algoritmo de ascenso de colinas se ha
implementado mediante un bucle que continuamente busca una solución
mejor. Termina cuando alcanza un pico donde ningún vecino tiene un
coste menor.
\begin{verbatim}
 while(continue){
	aux_sol=Vecina(sol1, mapa);
	if(aux_sol.get_cost() < sol1.get_cost()){
	  sol1.copiar(aux_sol);
	}
	else
	  continue = false;
      }
\end{verbatim}

Partimos de una solución en profundidad, ya que es la más simple y a
partir de esta solución vamos calculando los vecinos de 4 modos
distintos:
\begin{itemize}
\item Suprimir posición. Eliminamos una posición y construimos una
  solución nueva bordeando este punto.

  Esta variación era muy pequeña de modo que el algoritmo paraba muy
  pronto daba una solución que variaba muy poco de la solución
  original (en profundidad) y se optó por el siguiente punto.
\item Unión de dos puntos mediante algoritmo de línea de
  Bresenham. Con una modificación simple podemos utilizar este
  algoritmos para nuestro propósito ya que dando dos puntos aleatorios
  obtenemos el camino directo (diagonal igual a la distancia
  Manhattan) entre ellos.

  Utilizando esta función vecina el algoritmo de ascenso de colinas la
  solución tendía a ser siempre la misma, una diagonal directa entre
  el nodo inicio al final, de modo que se han introducido otros dos
  modos de encontrar soluciones vecinas.
\item Unión de dos puntos mediante ángulo recto. Igual que en el caso
  anterior partimos de dos puntos aleatorios y los unimos recorriendo
  todo el recorrido en la coordenada \emph{x} y luego la coordenada
  \emph{y}, generando un camino con forma de ángulo recto entre los
  dos puntos. Una variación de esto método es el recorrer primero el
  eje \emph{y} y luego el eje \emph{x}. La primera vecina sería unión
  por esquina derecha superior y la segunda por esquina izquierda inferior.
\end{itemize}
Los mejores resultados se han obtenido al mezclar las diferentes
maneras de generar soluciones vecinas.
\begin{verbatim}
  rand1 = (rand()%(sol_orig.size_posiciones()/2 -1))+1;
  rand2 = (rand()%(sol_orig.size_posiciones()/2 -1))+sol_orig.size_posiciones()/2;

  // unión Bresenham*
  sol_aux = sol_orig.vecina2(rand1, rand2, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }

  // unión angulo izq
  sol_aux = sol_orig.vecina3(rand1, rand2, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }

  // unión angulo dcho
  sol_aux = sol_orig.vecina4(rand1, rand2, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }
\end{verbatim}

Los puntos aleatorios se generan entre la primera mitad de los puntos
de la solución y la segunda mitad. Como esto tampoco generaba mucha
variación entre las soluciones se realiza otra pasada buscando puntos
entre cada cuarto de la solución.

\begin{verbatim}
  rand1 = (rand()%(sol_orig.size_posiciones()/4 -1))+1;
  rand2 = (rand()%(sol_orig.size_posiciones()/4 -1))+sol_orig.size_posiciones()/4;
\end{verbatim}

\textbf{Soluciones encontradas:}
\begin{figure}[!h]
  \center
  \includegraphics[scale=4.4]{colin1_50x50.png}
  \caption{Mapa 50x50 solucionado con algoritmo de ascensión de colinas}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=1.2]{colin1_200x200.png}
  \caption{Mapa 200x200 solucionado con algoritmo de ascensión de colinas}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.25]{colin1_1024x1024.png}
  \caption{Mapa 1024x1024 solucionado con algoritmo de ascensión de colinas}
\end{figure}

\subsubsection{Temple simulado}
El algoritmo de temple simulado viene a solventar los problemas con
los que se topa el ascenso de colinas, como son el encontrase con
mesetas, máximos locales o máximo local plano; es decir, no encontrar
solución vecina mejor aunque exista. Para ello no siempre optaremos
por la mejor solución vecina, utilizaremos una función aleatoria para
en ocasiones elegir un camino aunque no sea el mejor. Cuanto más
avance el algoritmo y menor deferencia haya entre las soluciones
vecinas, más cerca estaremos de una buena solución y será menos
probable el optar por una solución vecina peor.

\begin{verbatim}
 while(temp> 0){
    aux_sol=Vecina(sol1, mapa);
    diff = abs(sol1.get_cost()-aux_sol.get_cost());
    if (rand()%100 > pow(M_E,(-diff/temp))){
       if(aux_sol.get_cost() < sol1.get_cost())
          sol1.copiar(aux_sol);
       }
       Templar(temp, itera, diff);
       itera++;
}
\end{verbatim}

Partimos de una temperatura de 100 y va en disminución según la
función \emph{Templar} que irá disminuyendo la temperatura en función
del número de iteraciones y la diferencia entre las soluciones vecinas
y la actual.

\begin{verbatim}
void Templar(int &temp, int index, int diff){
  if(diff!=0)
    temp = temp  - index/diff;
}
\end{verbatim}

\textbf{Soluciones encontradas:}
\begin{figure}[!h]
  \center
  \includegraphics[scale=4.4]{enfria1_50x50.png}
  \caption{Mapa 50x50 solucionado con algoritmo de temple simulado}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=1.2]{enfria1_200x200.png}
  \caption{Mapa 200x200 solucionado con algoritmo de temple simulado}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.25]{enfria1_1024x1024.png}
  \caption{Mapa 1024x1024 solucionado con algoritmo de temple simulado}
\end{figure}

\clearpage

\subsection{Datos a comparar}
Indicar que en cada iteración la función \emph{Vecina} evalúa 6
soluciones vecinas y retorna a la función principal la mejor de ellas.

\textbf{Tabla resultados algoritmo Ascenso de colinas}
\begin{center}
   \begin{tabular}[!ht]{|c|c|c|c|c|} \hline
    \textbf{Imagen} & \textbf{MAc iteraciones} & \textbf{MAc
      nodos solución} & \textbf{MAc coste solución} & \textbf{MAc tiempo} \\
    \hline

    \textbf{50x50} & 14 & 100 & 442 & <0.01 seg \\ \hline
    \textbf{200x200} & 18 & 400 & 1123 & 0.01 seg \\ \hline
    \textbf{1024x1024} & 26 & 2148 & 7054 & 0.01 seg \\ \hline
  \end{tabular}
\end{center}

\textbf{Tabla resultados algoritmo Temple simulado}
\begin{center}
   \begin{tabular}[!ht]{|c|c|c|c|c|c|c|c|c|} \hline
    \textbf{Imagen} & \textbf{MEs iteraciones} & \textbf{MEs Nodos solución}  &
    \textbf{MEs coste solución} &\textbf{MEs tiempo}\\
    \hline

    \textbf{50x50} & 45 & 100 & 419 & 0.02 seg\\ \hline
    \textbf{200x200} & 86 & 401 & 905 & 0.04 seg \\ \hline
    \textbf{1024x1024} &360 & 2047 & 5514 & 0.92 seg \\ \hline
  \end{tabular}
\end{center}


\subsection{Gráficos comparativos Valor/Iteración}
En estas gráfica tenemos en el eje \emph{x} las iteraciones realizadas y en
el eje \emph{y} el coste de la solución retornada a la función
principal de búsqueda.

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.3]{50x50comp.png}
  \caption{gráfico del coste de las soluciones a lo largo de las
    iteraciones de búsqueda en un mapa de 50x50}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.3]{200x200comp.png}
  \caption{gráfico del coste de las soluciones a lo largo de las
    iteraciones de búsqueda en un mapa de 200x200}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.3]{1024x1024comp.png}
  \caption{gráfico del coste de las soluciones a lo largo de las
    iteraciones de búsqueda en un mapa de 1024x1024}
\end{figure}

\clearpage

\section*{Código implementado}
El código, así como el seguimiento de esta práctica está disponible en:

\url{https://code.google.com/p/ia-2012-13/}

\end{document}
